/*
 * Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
 */
package com.xinpan.exercise;

public class RecoverBinarySearchTree {
    public void recoverTree(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        NodeHolder hold = new NodeHolder();
        TreeNode pre = traPre(root.left, null, hold);
        
        if(pre != null && pre.val > root.val)
        {
            if(hold.f == null)
                hold.f = pre;
            hold.s = root;
               
        }
        traNext(root.right, root, hold);
        
        
        int val = hold.f.val;
        hold.f.val = hold.s.val;
        hold.s.val = val;
    }
    
    public TreeNode traPre(TreeNode root, TreeNode pre, NodeHolder hold)
    {
        if(root == null)
            return null;
        
        TreeNode re = traPre(root.left, pre, hold);
        if(re == null)
            re = pre;
        if(re != null && re.val > root.val)
        {
            if(hold.f == null)
                hold.f = re;
            hold.s = root;
        }
        TreeNode next = traNext(root.right, root, hold);
        if(next != null)
            return next;
        else
            return root;
    }
    
    public TreeNode traNext(TreeNode root, TreeNode pre, NodeHolder hold)
    {
        if(root == null)
            return null;
        
        TreeNode re = traPre(root.left, pre, hold);
        if(re == null)
            re = pre;
        if(re != null && re.val > root.val)
        {
            if(hold.f == null)
                hold.f = re;
            hold.s = root;
        }
        TreeNode next = traNext(root.right, root, hold);
        if(next != null)
            return next;
        else
            return root;
    }
    
    class NodeHolder
    {
        TreeNode f = null;
        TreeNode s = null;
        NodeHolder()
        {}
        
    }
}
